package algorithm.sort;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @Description：
 * @Author：LiDong
 * @Create：2021/4/19
 * @Version：1.0.0
 */
public class InsertSort {

    private static final Logger logger  = LoggerFactory.getLogger(InsertSort.class);

    /**
     * 1,5,3,4,2,6
     * <p>
     * 时间复杂度：最坏 O(n^2)
     * 时间复杂度：最好 O(n)
     */

    @Test
    public void test() {
        int[] arr = {1, 5, 3, 4, 2, 6};
        insertSort(arr);
        for (int i : arr) {
            logger.info(String.valueOf(i));
        }
    }


    public void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                // 待排序的元素
                int temp = arr[i];
                int j = i;
                while (j > 0 && temp < arr[j - 1]) {
                    arr[j] = arr[j - 1];
                    j--;
                }
                arr[j] = temp;
            }
        }
    }


}
